package leetcode_200;

import java.util.HashMap;
import java.util.Map;

/**
 *@author 周杨
 *LRUCache_146 在O(1)时间复杂度内完成缓存的操作 
 *describe:利用双向链表和map实现 AC 80%
 *2018年6月5日 下午4:08:48
 */
public class LRUCache_146 {
	class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
	
	private Node head;
    private Node tail;
    private Map<Integer, Node> map;
    private final int capacity;
    
    public LRUCache_146(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
    }  
    public int get(int key) {
        if (map == null || !map.containsKey(key)) {
            return -1;
        } else {
            Node node = map.get(key);
            updateOrder(node);
            return node.value;
        }
    }
    
     public void put(int key, int value) {
        if (!map.containsKey(key)) {
            if (map.size() == capacity) {
                removeLRUCache();
            }
            Node node = new Node(key, value);
            addNode(node);
            map.put(key, node);
        } else {
            Node node = map.get(key);
            updateOrder(node);
            node.value = value;
        }
    }
    
     private void addNode(Node node) {
        if (head == null) {
            head = node;
            tail = node;
            return;
        }

        node.next = head;
        head.prev = node;
        head = node;
    }
    
    private void updateOrder(Node node) {
        if (node == head) {//MRU, do nothing
            return;
        }

        if (node == tail) {//not head, but tail
            tail = node.prev;
            node.prev.next = null;
            node.prev = null;
            node.next = head;
            head.prev = node;
            head = node;
            return;
        }
        //not head, not tail
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.next = head;
        node.prev = null;
        head.prev = node;
        head = node;
    }
    
    private void removeLRUCache() {
        map.remove(tail.key);
        if (head == tail) {
            head = null;
            tail = null;
            return;
        }

        Node newTail = tail.prev;
        tail.prev = null;
        newTail.next = null;
        tail = newTail;
    }
    
    
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
